package com.buddy.learn.algorithm.simple;

/**
 * @author Buddy
 * @date 2021/5/17
 */
public class _最长回文子串_中心扩散 {


    /*
     * 给你一个字符串 s，找到 s 中最长的回文子串。
     * 如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串
     * 例如对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么“ababa” 一定是回文串，
     * 这是因为它的首尾两个字母都是“a”。
     */
    public static void main(String[] args) {
//        String s = "cbbd";
//        String s = "ac";
//        String s = "bb";
        String s = "aaaa";
        String res = getHuiWen(s);
        System.out.println(res);
    }

    private static String getHuiWen(String s) {
        if (s.length() < 2) {
            return s;
        }
        char[] chars = s.toCharArray();
        int maxLen = 1;
        String maxStr = s.charAt(0) + "";
        for (int i = 1; i < chars.length; i++) {
            char pre = chars[i - 1];
            char cur = chars[i];
            if (pre == cur) {
                // 这里是一个回文，以这里为中心进行扩展
                int[] range = getRange(i - 1, i, chars);
                int len = getLen(range);
                if (len > maxLen) {
                    maxLen = len;
                    if ((range[1] + 1) > chars.length) {
                        maxStr = s.substring(range[0]);
                    } else {
                        maxStr = s.substring(range[0], range[1] + 1);
                    }

                }
            }
            if (i + 1 < chars.length) {
                char next = chars[i + 1];
                if (pre == next) {
                    // 这里是一个回文，以这里为中心进行扩展
                    int[] range = getRange(i - 1, i + 1, chars);
                    int len = getLen(range);
                    if (len > maxLen) {
                        maxLen = len;
                        if ((range[1] + 1) > chars.length) {
                            maxStr = s.substring(range[0]);
                        } else {
                            maxStr = s.substring(range[0], range[1] + 1);
                        }
                    }
                }
            }
        }
        return maxStr;
    }

    private static int getLen(int[] range) {
        return range[1] - range[0] + 1;
    }

    private static int[] getRange(int left, int right, char[] chars) {
        int[] res = new int[]{left, right};
        while (left < right && left > 0 && right < chars.length) {
            char L = chars[left];
            char R = chars[right];
            if (L == R) {
                left = left + 1;
                right = right - 1;
            } else {
                res = new int[]{left, right};
            }
        }
        return res;
    }

}
